package solutions.leetcode.normal;

import solutions.lib.BaseSolution;

/**
 * @author lizhidong
 * <a href="https://leetcode-cn.com/problems/previous-permutation-with-one-swap/">1053. 交换一次的先前排列</a>
 */
public class Solution1053 extends BaseSolution {

    public int[] prevPermOpt1(int[] arr) {
        int p = arr.length - 1;
        while (p > 0) {
            if (arr[p] >= arr[p - 1]) {
                p--;
            } else {
                break;
            }
        }
        if (p == 0) {
            return arr;
        }
        int left = p - 1;
        int right = p;
        while (true) {
            if (p + 1 < arr.length && arr[p + 1] < arr[left]) {
                p++;
                if (arr[p] > arr[right]) {
                    right = p;
                }
            } else {
                int t = arr[right];
                arr[right] = arr[left];
                arr[left] = t;
                break;
            }
        }
        return arr;
    }

    public static void main(String[] args) {
        Solution1053 solution = new Solution1053();
        printVals(solution.prevPermOpt1(new int[] {
                3,1,1,3
        }));
    }
}